Shortest path visiting all nodes [BFS]

Time: O(Nx2^N); Space: O(Nx2^N); hard

An undirected, connected graph of N nodes (labeled 0, 1, 2, …, N-1) is given as graph.

graph.length = N, and j != i is in the list graph[i] exactly once, if and only if nodes i and j are connected.

Return the length of the shortest path that visits every node. You may start and stop at any node, you may revisit nodes multiple times, and you may reuse edges.

Example 1:

Input: graph = [[1,2,3],[0],[0],[0]]

Output: 4

Explanation:

  • One possible path is [1,0,2,0,3]

Example 2:

Input: graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]

Output: 4

Explanation:

  • One possible path is [0,1,4,2,3]

Constraints:

  • 1 <= len(graph) <= 12

  • 0 <= len(graph[i]) < len(graph)

1. Breadth First Search [O(Nx2^N), O(Nx2^N)]

Intuition

A path ‘state’ can be represented as the subset of nodes visited, plus the current ‘head’ node. Then, the problem reduces to a shortest path problem among these states, which can be solved with a breadth-first search.

Algorithm

Let’s call the set of nodes visited by a path so far the cover, and the current node as the head. We’ll store the cover states using set bits: k is in the cover if the kth bit of cover is 1.

For states state = (cover, head), we can perform a breadth-first search on these states. The neighbors are (cover | (1 << child), child) for each child in graph[head].

If at any point we find a state with all set bits in it’s cover, because it is a breadth-first search, we know this must represent the shortest path length.

[14]:

import collections

class Solution1(object):

    def shortestPathLength(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: int
        """
        N = len(graph)
        queue = collections.deque((1 << x, x) for x in range(N))
        dist = collections.defaultdict(lambda: N*N)
        for x in range(N):
            dist[1 << x, x] = 0

        while queue:
            cover, head = queue.popleft()
            d = dist[cover, head]
            if cover == 2**N - 1:
                return d

            for child in graph[head]:
                cover2 = cover | (1 << child)
                if d + 1 < dist[cover2, child]:
                    dist[cover2, child] = d + 1
                    queue.append((cover2, child))

[15]:

s = Solution1()

graph = [[1,2,3],[0],[0],[0]]
assert s.shortestPathLength(graph) == 4

graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
assert s.shortestPathLength(graph) == 4

2. Dynamic Programming [O(Nx2^N), O(Nx2^N)]

[16]:

import collections

class Solution2(object):
    """
    Time: O(N*2^N)
    Space: O(N*2^N)
    """
    def shortestPathLength(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: int
        """
        dp = [[float("inf")]*(len(graph))
              for _ in range(1 << len(graph))]
        q = collections.deque()

        for i in range(len(graph)):
            dp[1 << i][i] = 0
            q.append((1 << i, i))

        while q:
            state, node = q.popleft()
            steps = dp[state][node]

            for nei in graph[node]:
                new_state = state | (1 << nei)
                if dp[new_state][nei] == float("inf"):
                    dp[new_state][nei] = steps+1
                    q.append((new_state, nei))

        return min(dp[-1])

[17]:

s = Solution2()

graph = [[1,2,3],[0],[0],[0]]
assert s.shortestPathLength(graph) == 4

graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
assert s.shortestPathLength(graph) == 4